Digital Images
An image is typically represented digitally as a rectangular array of pixels with each pixel having one of a restricted set of legitimate pixel values. Digital images may be black and white in which case the restricted set of legitimate pixel values is used to encode an optical density or luminance score. Digital images may also be colour where the restricted set of pixel values may encode an optical density or intensity score for each of a number of colour channels—for example Cyan, Magenta, Yellow and Black (CMYK) or Red, Green and Blue (RGB).
Digital images are common where the image value per pixel per colour channel is an 8 bit unsigned number—providing intensity values in the range 0 through 255. Such images are often called “continuous tone” images because of the reasonably large number (256) of legitimate intensity values.
Digital Halftoning
By contrast, digital images are often printed on devices which provide a more limited variation in intensity or colour representation per pixel. For example, many Bubble Jet printers only provide the ability to print or not print a dot of each of a Cyan, Magenta, Yellow and Black ink at each pixel position.
In order to print a digital image on a printer with lower colour resolution than the digital image, it is necessary to use the original image to generate an image with the required lower colour resolution such that the generated image has a similar appearance to the original image. This process of generating a digital image of similar appearance where each pixel colour value is within a smaller set of legitimate pixel colour values, is known as digital halftoning.
For ease of explanation, digital halftoning is hereafter described for the case where the input image is a single colour channel, 8 bit per pixel image and the halftoned image is a 1 bit per pixel (bi-level) image. The input image values are known as greyscale values or grey levels. Extensions of digital halftoning from this monochrome bi-level case to cases where the halftoned image pixels have more than 2 legitimate output values (multi-level halftoning) and extensions to digital halftoning of colour images can be performed. See for example, “Digital Halftoning” Ulichney R., MIT Press, 1987, pp 340–342.
Consider the case of a single colour channel, 8 bit per pixel, image which is halftoned to generate a 1 bit per pixel (bi-level) image which is printable on a black and white bubble jet printer, for which each pixel of the halftoned image has one of 2 legitimate pixel values, a “no dot” value and a “dot” value.
An image region in the halftoned image will print as a minimum optical density (“fully white”) region when all pixels of the region have the “no dot” value corresponding to non-placement of an ink dot; it will print as a maximum optical density (“fully black”) region when all pixels of the region have the “dot” value corresponding to placement of an ink dot; and it will print as an intermediate optical density (halftone) region when some of the pixels of the region have the “no dot” value and some of the pixels have the “dot” value.
A highlight (near white) region in the halftoned image will have only a few of the pixels with the “dot” value—in these regions the “dot” halftone output value is the minority or exceptional result. A shadow (near black) region will have only a few of the pixels with the “no dot” value—in these regions the “no dot” halftone output value is the minority or exceptional result.
The role of the halftoning process is to generate the printable image so that an appropriate number of ink dots will print in appropriate pixel positions so that there is a good match between the optical density of image regions in the original image and the average optical density of the matching image regions in the printed image.
Error Diffusion
Error diffusion is a digital halftoning method originally developed by Floyd and Steinberg and described in the publication “An Adaptive Algorithm for Spatial Greyscale”, Proceedings of the SID 17/2, pp 75–77 (1976), Error diffusion as developed by Floyd and Steinberg is hereafter described as “standard error diffusion”.
An overview of standard error diffusion is now provided.
The standard error diffusion algorithm processes pixels line by line from the top of the image to the bottom of the image. Each line (or “scanline”) is processed one pixel at a time from left to right.
The standard error diffusion algorithm employs a pixel decision rule in which a modified input image pixel value is compared against a threshold value. If the pixel's modified input value is less than the threshold, then the pixel's halftone output value is assigned to be the lower halftone output value; and if it is greater, then the pixel's halftone output value is assigned to be the higher halftone output value.
Following determination of the pixel halftone output value, an error is determined for the pixel as the difference between the pixel's modified input value and the pixel's halftone output value. The error is distributed to neighbouring, as yet unprocessed, pixels according to a set of weighting coefficients.
A pixel's modified input value is the sum of the pixel's input image value and a neighbourhood error value for the pixel. The neighbourhood error for a pixel is the sum of the errors distributed to that pixel from previously processed neighbouring pixels.
The set of weighting coefficients is known as an error diffusion mask. Each weighting coefficient of the error diffusion mask is associated with a pixel offset. When a pixel is processed, the error distributed from the pixel to an as yet unprocessed pixel is the pixel error multiplied by the weight corresponding to the offset from the pixel to the unprocessed pixel.
Note that the error at a pixel which is distributed to its neighbours can be considered as a sum of the neighbourhood error at the pixel and the pixel-only error being the pixel's input value less the pixel's halftone output value.
The error diffusion mask described by Floyd and Steinberg is shown in FIG. 1. The error at a pixel is distributed in the proportions 7/16, 1/16, 5/16 and 3/16 to 4 neighbouring pixels which are as yet unprocessed as indicated in the diagram. FIG. 1 shows an error diffusion mask 100 in which an error for a current pixel 108 is distributed in the proportions indicated to four neighbouring pixels eg. 106 in the fractional proportions shown. Previously processed pixels eg. 110 are shown using a shaded representation, and it is noted that the current pixel 108 lies on a current scanline 102. Previously processed pixels lie above a bold line 104 in FIG. 1, and a scanline processing direction is depicted by a horizontal arrow 112.
It is noted that the sum of the weighting coefficients is 1. As a result 100% of a pixel's error is transferred to its neighbouring pixels. If the sum of weighting coefficients were greater than 1, then error would be amplified and could build up without bound. If the sum of weighting coefficients were less than 1, then error would be reduced. By having the sum of weighting coefficients equal to unity, the average intensity of a region of the halftoned image tends to match the average intensity of that region in the input image which is a very desirable characteristic of a halftoning process.
In implementations of standard error diffusion where multiplication of error by a weighting coefficient results in significant rounding errors, it is necessary to co-ordinate the calculation of error distributions to neighbouring pixels so that effectively 100% of current pixel error is transferred on. This can be achieved by determining error distributions to all but one of the neighbouring pixels by multiplication by a weight and determining the error distribution to the remaining neighbouring pixel by subtracting the other error distributions from the total error to be distributed.
For improved execution speed, error distributions corresponding to a particular pixel error value are often determined in advance and retrieved from a look up table.
In the Floyd and Steinberg error diffusion mask, the pixels which receive error distributions from a current pixel are on the current scanline and succeeding scanline only. An implementation of error diffusion with this mask requires the use of a single “line store” memory to store neighbourhood error values. The memory is referred to as a “line store” because it is required to store a neighbourhood error value for each pixel of a scanline. Many of the modifications to error diffusion which are referred to below are achieved at the cost of extra memory for an additional one or more line stores.
Error diffusion algorithms are used in the printing and display of digital images. Many modifications to the standard error diffusion algorithm have been developed.
Worm Artifacts
The error diffusion algorithm suffers from the disadvantage that in image regions of very low or very high intensity, it generates a pattern of image values in the halftoned image which are poorly spread—the exceptional values are concentrated in wavy lines. These patterns can be very noticeable and distracting to a viewer of the image—they are often known as “worm” artifacts.
FIG. 5 shows a section of a halftone output image generated by Floyd Steinberg error diffusion which shows worm artifacts. This halftone output was generated by bi-level halftoning of an 8 bit per pixel monochrome source image with a constant grey value of 253. FIG. 5 shows a halftone output image 500 which, as noted, shows worm artifacts, as illustrated by, for example, pairs of pixels 502, and a quadruplet of pixels 504.
Modifications to error diffusion have been developed to reduce worm artifacts.
Prior Art Methods of Reducing Worm Artifacts
One method of reducing worm artifacts is by addition of some randomisation. The randomisation may be achieved by adding noise to the input image, by adding noise to the thresholds or by randomising the error distribution to neighbouring pixels. A large amount of noise or randomisation can be added to fully avoid worm artifacts; however, this also seriously degrades the halftoned image.
Another method of reducing worm artifacts is to vary the direction in which scanlines are processed. By way of example, U.S. Pat. No. 4,955,065 titled “System for Producing Dithered Images from Continuous-tone Image Data” to Ulichney discloses error diffusion with perturbed weighting coefficients and bi-directional scanline processing.
Another method of reducing worm artifacts is by use of larger error diffusion masks. For example, in “Error Diffusion Algorithm with Reduced Artifacts”, Eschbach R., Proceedings of the IS&T's 45th Annual Conference, May 10–15, 1992, either a large or a small error diffusion mask is used depending on the input image grey level. The large error diffusion mask is suited to use in image regions of very high or very low greyscale, reducing the worm artifacts in those regions. A disadvantage of this method is that large error diffusion masks which distribute error to pixels of more than 1 succeeding scanline require additional error line stores and associated processing.
A further method of reducing worm artifacts by use of an “extended distribution set” style of error diffusion mask is described in U.S. Pat. No. 5,353,127, titled “Method for Quantization Gray Level Pixel Data with Extended Distribution Set” to Shiau and Fan. This patent describes error diffusion masks including pixel positions of only the current and succeeding scanline with additional pixel positions on the next scanline to the left of (that is, behind) the current pixel.
FIG. 2 shows an error diffusion mask of U.S. Pat. No. 5,353,127. An error for a current pixel 208 is, in this case, distributed to five neighbouring pixels eg. 206, where each of these five pixels receives a fractional proportion of the error as indicated. Scanline processing is from left to right as depicted by an arrow 212, and previously processed pixels, eg. 210, are full shaded and lie above a bold line 204. The current pixel 208 lines on a current scanline 202. While this method is successful at reducing worm artifacts and only requires a single error line store, worm artifacts are still evident for bi-level halftoning of 8 bit grey scale image data, as can be seen in FIG. 6.
FIG. 6 shows example halftone output generated by bi-level error diffusion, using the mask of FIG. 2, for an 8 bit per pixel source image with constant grey value of 253, FIG. 6 shows an image 600 which exhibits worm artifacts as exemplified by reference numerals 602 and 604.
Prior Art Methods of Preventing Artifacts
While the above methods are successful in reducing worm artifacts, complete prevention of worm artifacts can also be achieved.
One method of preventing worm artifacts is by modulating threshold values. U.S. Pat. No. 5,535,019 titled “Error diffusion halftoning with homogeneous response in high/low intensity image regions” to Eschbach discloses a modification to error diffusion which adjusts the error diffusion threshold according to the halftone output and according to the input intensity using a threshold impulse function, for the purpose of preventing worm artifacts.
Another modification to error diffusion which prevents worm artifacts by threshold modulation is described in “A serpentine error diffusion kernel with threshold modulation for homogeneous dot distribution”, Hong D., Kim C., Japan Hardcopy '98 pp 363–366, 1998 which is also published in IS&T's Recent Progress In Digital Halftoning II (1999) pp 306–309.
Another method of preventing worm artifacts is the addition of grey level dependent periodic noise to the input image, described in “Modified error diffusion with smoothly dispersed dots in highlight and shadow”, Japan Hardcopy '98 pp 379–382, 1998 which is also published in IS&T's Recent Progress In Digital Halftoning II (1999) pp 310–313.
Another method of preventing worm artifacts is by imposing output position constraints. An example of this method is provided in “An error diffusion algorithm with output constraints for homogeneous highlight and shadow dot distribution”, Marcu G., Proceedings of SPIE, Vol 3300, pp 341–352 (1998).
Disadvantages of Prior Art Methods of Preventing Worm Artifacts
In many cases the desirability of a halftoning algorithm is determined by how fast it executes and how easy it is to implement. For example, in software implementations in a printer driver on a general purpose computer, the algorithm execution speed is very important; whereas in special purpose hardware, the algorithm complexity and memory usage are very important because they relate strongly to the expense of the circuitry.
Use of additional line store memory by a halftoning algorithm generally indicates that it will execute slower in software and is more expensive to implement in hardware.
The modification to error diffusion disclosed in U.S. Pat. No. 5,535,019 to Eschbach requires use of memory for an additional line store to store threshold adjustment values generated by preceding scanlines for use by a current scanline. The modification also requires additional processing including addition of threshold impulse values and dampening of threshold values transferred to subsequent scanlines.
The modification to error diffusion described in the previously mentioned paper titled “A serpentine error diffusion kernel with threshold modulation for homogeneous dot distribution” also requires use of an additional line store memory to store threshold adjustment values. Additional processing is also required to diffuse threshold adjustment values.
The modification to error diffusion described in the previously mentioned paper titled “Modified error diffusion with smoothly dispersed dots in highlight and shadow” requires memory for additional line stores to store several neighbouring scanlines of processed input image data from which filtered input image values for a current scanline are determined; the filtered input image values arc used in turn to determine the noise to be added to the input image data.
The modification to error diffusion described in the previously mentioned paper titled “An error diffusion algorithm with output constraints for homogeneous highlight and shadow dot distribution” requires memory for additional lines stores to store halftoned image data for several previously processed scanlines. This modification also includes processing to exclude minority halftone output results when that result is present in a certain portion of the previously processed scanlines.
In summary, all the modifications listed above which prevent worm artifacts in error diffusion require use of additional line store memory together with the processing associated with use of that additional memory.
References made to prior art documents in the present description in no way constitutes an acknowledgment that the prior art documents are part of the common general knowledge.